// 队列 + 宽搜
// N叉树/二叉树 的层序遍历：借助一个队列实现
// 层序遍历的方式 结合 堆的思维（用数组存储节点），计算二叉树的宽度
// 借助队列实现二叉树的层序遍历，在每一层中找最大值

// 例题 4：
// 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
//
//        示例1：
//
//        输入: root = [1,3,2,5,3,null,9]
//        输出: [1,3,9]
//        示例2：
//
//        输入: root = [1,2,3]
//        输出: [1,3]
//
//        提示：
//
//        二叉树的节点个数的范围是 [0,104]
//        -231 <= Node.val <= 231 - 1

// 解题思路：
// 在层序遍历的基础上，找出每一层的最大值


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LargestValues {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int maxValue = Integer.MIN_VALUE;
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                maxValue = Math.max(maxValue, node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            ret.add(maxValue);
        }
        return ret;
    }
}
